import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 3
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 1
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 7667, C = 5292
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
1640 | is_connectable
82 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
123 | is_connected_step
3362 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 600.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5292 rows, 7667 columns and 25297 nonzeros
Model fingerprint: 0x44b6d43b
Model has 820 general constraints
Variable types: 2460 continuous, 5207 integer (5207 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 89 rows and 1768 columns
Presolve time: 0.08s
Presolved: 5203 rows, 5899 columns, 25440 nonzeros
Variable types: 2460 continuous, 3439 integer (3439 binary)
Found heuristic solution: objective 76211.586734
Root relaxation: objective 1.196505e+03, 5276 iterations, 0.12 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1196.50494 0 140 76211.5867 1196.50494 98.4% - 0s
H 0 0 38744.687726 1196.50494 96.9% - 0s
0 0 2709.97670 0 221 38744.6877 2709.97670 93.0% - 0s
0 0 2740.62084 0 239 38744.6877 2740.62084 92.9% - 0s
H 0 0 21181.958577 2740.62084 87.1% - 0s
0 0 2742.96585 0 231 21181.9586 2742.96585 87.1% - 0s
0 0 2743.17269 0 238 21181.9586 2743.17269 87.0% - 0s
0 0 2785.20392 0 341 21181.9586 2785.20392 86.9% - 0s
0 0 2787.60608 0 343 21181.9586 2787.60608 86.8% - 0s
0 0 2788.75829 0 334 21181.9586 2788.75829 86.8% - 0s
0 0 2788.77649 0 327 21181.9586 2788.77649 86.8% - 0s
0 0 2808.89172 0 268 21181.9586 2808.89172 86.7% - 1s
H 0 0 21029.629265 2808.89172 86.6% - 1s
0 0 2818.40848 0 328 21029.6293 2818.40848 86.6% - 1s
0 0 2819.24128 0 326 21029.6293 2819.24128 86.6% - 1s
0 0 2819.27480 0 330 21029.6293 2819.27480 86.6% - 1s
0 0 2832.79742 0 346 21029.6293 2832.79742 86.5% - 1s
0 0 2839.99093 0 366 21029.6293 2839.99093 86.5% - 1s
0 0 2842.16565 0 367 21029.6293 2842.16565 86.5% - 1s
0 0 2842.19274 0 369 21029.6293 2842.19274 86.5% - 1s
0 0 2845.90998 0 407 21029.6293 2845.90998 86.5% - 1s
0 0 2846.43946 0 408 21029.6293 2846.43946 86.5% - 1s
0 0 2850.39054 0 411 21029.6293 2850.39054 86.4% - 1s
0 0 2850.69205 0 412 21029.6293 2850.69205 86.4% - 1s
0 0 2851.58484 0 395 21029.6293 2851.58484 86.4% - 1s
0 0 2851.58484 0 231 21029.6293 2851.58484 86.4% - 2s
H 0 0 18491.570643 2871.98667 84.5% - 2s
0 2 2871.98667 0 231 18491.5706 2871.98667 84.5% - 2s
H 73 63 17002.343259 3232.02967 81.0% 330 4s
H 103 81 16837.031118 3232.02967 80.8% 279 4s
H 115 85 16677.512666 3232.02967 80.6% 256 5s
H 116 85 16480.013577 3232.02967 80.4% 256 5s
H 121 85 16267.498262 3232.02967 80.1% 263 5s
H 142 102 16188.364911 3232.02967 80.0% 260 5s
H 151 108 15909.279956 3232.02967 79.7% 262 5s
H 229 154 15840.094834 3232.02967 79.6% 220 6s
H 230 154 15706.358301 3232.02967 79.4% 220 6s
H 526 343 15702.395387 3232.02967 79.4% 168 7s
H 580 358 15702.365318 3232.02967 79.4% 170 8s
H 582 358 15658.932881 3232.02967 79.4% 171 8s
H 599 358 15647.179006 3232.02967 79.3% 173 8s
H 649 385 15518.933207 3232.02967 79.2% 170 8s
H 797 422 15518.933192 3232.02967 79.2% 160 9s
1024 457 5587.41187 63 213 15518.9332 3232.02967 79.2% 159 10s
H 1088 457 15518.933081 3232.02967 79.2% 154 10s
H 1224 499 15518.933054 3232.02967 79.2% 149 11s
1910 889 12727.1682 113 262 15518.9331 3232.02967 79.2% 127 15s
1924 900 3232.02967 15 264 15518.9331 3232.02967 79.2% 136 22s
1940 905 4208.32250 18 345 15518.9331 3232.02967 79.2% 143 25s
H 1993 866 15518.933046 3674.25063 76.3% 151 27s
H 2093 806 15518.933023 4121.62445 73.4% 156 29s
2140 789 5726.35151 28 198 15518.9330 4222.65069 72.8% 159 30s
H 2184 745 15518.932992 4222.65069 72.8% 161 30s
H 2186 712 15518.932938 4222.65069 72.8% 161 31s
H 2193 673 15518.932928 4222.65069 72.8% 162 31s
2762 696 5355.94864 22 270 15518.9329 4828.37638 68.9% 165 35s
H 3590 636 15476.122400 6425.61572 58.5% 165 39s
3592 702 6554.88524 31 211 15476.1224 6425.61572 58.5% 165 40s
4696 804 9024.27555 30 166 15476.1224 8098.97839 47.7% 165 45s
H 4959 786 15476.122388 8609.32282 44.4% 164 45s
5984 478 infeasible 34 15476.1224 10744.7230 30.6% 163 50s
13703 1731 cutoff 51 15476.1224 15401.9399 0.48% 82.0 55s
H13943 1731 15476.122325 15401.9619 0.48% 80.6 55s
H18550 1337 15476.122314 15426.8792 0.32% 62.0 58s
21697 573 15460.5608 45 27 15476.1223 15446.3044 0.19% 53.7 60s
Cutting planes:
Gomory: 34
Cover: 125
Implied bound: 19
MIR: 60
Flow cover: 164
GUB cover: 1
Inf proof: 3
Zero half: 16
RLT: 97
Relax-and-lift: 28
Explored 24057 nodes (1186935 simplex iterations) in 60.77 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 15476.1 15518.9 15518.9 ... 15702.4
Optimal solution found (tolerance 1.00e-04)
Best objective 1.547612231358e+04, best bound 1.547612231358e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.5 | 4.000000e+00 | 8.500000 |
| 1 | 1 | Borås | False | False | 0.7 | 1.030000e+01 | 10.999999 |
| 2 | 2 | Eskilstuna | True | False | 1.1 | 6.190000e+01 | 63.000000 |
| 3 | 3 | Falun | False | False | 2.3 | 6.021628e-12 | 2.300000 |
| 4 | 4 | Gävle | False | False | 1.0 | 3.130000e+01 | 32.300000 |
| 5 | 5 | Göteborg | False | False | 5.8 | 5.240253e-13 | 5.800000 |
| 6 | 6 | Halmstad | False | False | 3.4 | 6.099999e+00 | 9.499999 |
| 7 | 7 | Haparanda | False | False | 4.6 | 0.000000e+00 | 4.600000 |
| 8 | 8 | Helsingborg | False | False | 2.2 | 3.900000e+00 | 6.099999 |
| 9 | 9 | Hudiksvall | False | False | 3.9 | 2.740000e+01 | 31.300000 |
| 10 | 10 | Jönköping | False | False | 1.2 | 2.389866e-12 | 1.200000 |
| 11 | 11 | Kalmar | False | False | 4.0 | 5.613288e-13 | 4.000000 |
| 12 | 12 | Karlskrona | False | False | 1.6 | 8.077983e-13 | 1.600000 |
| 13 | 13 | Karlstad | False | False | 0.9 | 6.516565e-12 | 0.900000 |
| 14 | 14 | Kiruna | False | False | 4.0 | 0.000000e+00 | 4.000000 |
| 15 | 15 | Kristianstad | False | False | 3.0 | 5.103743e-07 | 3.000001 |
| 16 | 16 | Lidköping | False | False | 1.2 | 1.340000e+01 | 14.600000 |
| 17 | 17 | Linköping | False | False | 4.1 | 1.800000e+00 | 5.900000 |
| 18 | 18 | Luleå | False | False | 2.0 | 1.310000e+01 | 15.100000 |
| 19 | 19 | Malmö | False | False | 2.6 | 1.300000e+00 | 3.900001 |
| 20 | 20 | Motala | False | False | 2.4 | 2.010000e+01 | 22.500000 |
| 21 | 21 | Norrköping | False | False | 1.7 | 9.849899e-13 | 1.700000 |
| 22 | 22 | Nyköping | False | False | 4.6 | 7.915446e-12 | 4.600000 |
| 23 | 23 | Sandviken | False | False | 4.5 | 7.140954e-13 | 4.500000 |
| 24 | 24 | Skellefteå | False | False | 4.4 | 1.510000e+01 | 19.500000 |
| 25 | 25 | Skövde | False | False | 2.5 | 1.100000e+01 | 13.500000 |
| 26 | 26 | Stockholm | False | False | 7.0 | 5.684342e-13 | 7.000000 |
| 27 | 27 | Sundsvall | False | False | 0.7 | 2.670000e+01 | 27.400000 |
| 28 | 28 | Trelleborg | False | False | 1.3 | 3.749556e-12 | 1.300000 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 5.800000e+00 | 9.800000 |
| 30 | 30 | Umeå | False | False | 3.2 | 1.950000e+01 | 22.700000 |
| 31 | 31 | Uppsala | False | False | 1.9 | 3.230000e+01 | 34.200000 |
| 32 | 32 | Varberg | False | False | 0.8 | 9.499999e+00 | 10.300000 |
| 33 | 33 | Vetlanda | False | False | 2.1 | 1.090000e+01 | 13.000001 |
| 34 | 34 | Vänersborg | False | False | 3.6 | 9.800000e+00 | 13.400000 |
| 35 | 35 | Västervik | False | False | 1.8 | 1.492140e-12 | 1.800000 |
| 36 | 36 | Västerås | True | False | 1.4 | 1.110000e+02 | 112.400000 |
| 37 | 37 | Växjö | False | False | 2.3 | 4.600001e+00 | 6.900001 |
| 38 | 38 | Örebro | True | True | 4.1 | 1.639000e+02 | 55.600000 |
| 39 | 39 | Örnsköldsvik | False | False | 3.1 | 2.270000e+01 | 25.800000 |
| 40 | 40 | Östersund | False | False | 0.9 | 1.596057e-12 | 0.900000 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 19.500000 | 731.139160 | 111 |
| 1 | Eskilstuna | Västerås | CORE | 63.000000 | 430.000000 | 43 |
| 2 | Gävle | Hudiksvall | SUB | -31.300000 | 1278.724564 | 118 |
| 3 | Skövde | Örebro | SUB | 13.500000 | 657.432739 | 132 |
| 4 | Lidköping | Örebro | SUB | 14.600000 | 841.276343 | 148 |
| 5 | Stockholm | Västerås | SUB | 7.000000 | 234.688115 | 101 |
| 6 | Karlskrona | Växjö | SUB | 1.600000 | 62.121900 | 102 |
| 7 | Motala | Örebro | SUB | 22.500000 | 637.862087 | 92 |
| 8 | Boden | Kiruna | SUB | -4.000000 | 637.913000 | 291 |
| 9 | Sundsvall | Östersund | SUB | -0.900000 | 70.870188 | 166 |
| 10 | Halmstad | Helsingborg | SUB | -6.099999 | 145.447326 | 79 |
| 11 | Umeå | Örnsköldsvik | SUB | 22.700000 | 849.479945 | 111 |
| 12 | Boden | Luleå | SUB | 8.500000 | 58.656839 | 32 |
| 13 | Eskilstuna | Örebro | CORE | -55.600000 | 830.000000 | 83 |
| 14 | Karlstad | Örebro | SUB | 0.900000 | 29.229970 | 77 |
| 15 | Halmstad | Varberg | SUB | 9.499999 | 167.432219 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -13.400000 | 206.938975 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 9.800000 | 39.823253 | 21 |
| 18 | Linköping | Motala | SUB | 5.900000 | 77.952787 | 51 |
| 19 | Sandviken | Västerås | SUB | 4.500000 | 174.172927 | 110 |
| 20 | Falun | Västerås | SUB | 2.300000 | 115.327746 | 128 |
| 21 | Linköping | Västervik | SUB | -1.800000 | 64.378861 | 97 |
| 22 | Sundsvall | Örnsköldsvik | SUB | -25.800000 | 1177.683887 | 127 |
| 23 | Jönköping | Motala | SUB | 1.200000 | 52.590906 | 108 |
| 24 | Eskilstuna | Nyköping | SUB | -4.600000 | 119.995513 | 83 |
| 25 | Vetlanda | Växjö | SUB | -6.900001 | 143.305438 | 72 |
| 26 | Borås | Varberg | SUB | -10.300000 | 260.758771 | 84 |
| 27 | Haparanda | Luleå | SUB | 4.600000 | 210.858555 | 124 |
| 28 | Luleå | Skellefteå | SUB | 15.100000 | 742.410242 | 133 |
| 29 | Kristianstad | Växjö | SUB | 3.000001 | 134.707658 | 120 |
| 30 | Motala | Vetlanda | SUB | -13.000000 | 654.828175 | 135 |
| 31 | Uppsala | Västerås | SUB | 34.200000 | 755.020135 | 78 |
| 32 | Gävle | Uppsala | SUB | 32.300000 | 484.711112 | 60 |
| 33 | Helsingborg | Malmö | SUB | -3.900000 | 67.318052 | 60 |
| 34 | Göteborg | Uddevalla | SUB | 5.800000 | 117.417503 | 70 |
| 35 | Västerås | Örebro | CORE | 112.400000 | 930.000000 | 93 |
| 36 | Malmö | Trelleborg | SUB | -1.300000 | 18.150077 | 34 |
| 37 | Hudiksvall | Sundsvall | SUB | -27.400000 | 641.652314 | 81 |
| 38 | Eskilstuna | Norrköping | SUB | -1.700000 | 65.379519 | 102 |
| 39 | Borås | Skövde | SUB | 10.999999 | 384.262758 | 105 |
| 40 | Kalmar | Vetlanda | SUB | 4.000000 | 174.202753 | 119 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 2190.000 subnet = 13286.122 ------------------ total = 15476.122
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))